package DFS;

/**
 * @Classname JZ12矩阵中的路径
 * @Description
 * 设函数 check(i,j,k) 表示判断以网格的 (i,j) 位置出发，能否搜索到单词 word[k..]，其中 word[k..]
 * 表示字符串 word从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。
 *
 * 函数 check(i,j,k) 的执行步骤如下：
 *   如果 board[i][j]≠s[k],当前字符不匹配，直接返回 false。
 *   如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。
 *   否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，否则返回 false
 * 这样，我们对每一个位置 (i,j)都调用函数 check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。
 * @Date 2022/12/6 9:54
 * @Created by xjl
 */
public class JZ12矩阵中的路径 {

    int[][] dict=new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * @description 使用回溯算法来实现
      * @param: board
     * @param: word
     * @date: 2022/12/6 10:12
     * @return: boolean
     * @author: xjl
    */
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        // 判断时候访问的标志
        boolean[][] visited = new boolean[h][w];
        // 逐个遍历来实现
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // 数组传递  访问标志位  当前的i j的位置  目标word  当前的匹配的字符数
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * @description
      * @param: board 查找的数组
     * @param: visited 是否已经访问了的数据
     * @param: i 当前的位置坐标
     * @param: j 当前的位置坐标
     * @param: word 目标单词
     * @param: k 当前匹配的字符数
     * @date: 2022/12/6 10:15
     * @return: boolean
     * @author: xjl
    */
    private boolean check(char[][] board, boolean[][] visited, int i, int j, String word, int k) {
        // 如果 board[i][j]≠s[k],当前字符不匹配，直接返回 false。
        if (board[i][j] != word.charAt(k)) {
            return false;
        } else if (k == word.length() - 1) {
            // 表示匹配完成了 就返回true
            return true;
        }
        // 访问当前元素
        visited[i][j] = true;
        boolean result = false;
        for (int[] dir : dict) {
            int newi = i + dir[0],newj = j + dir[1];
            // 保证需要在矩阵的内部
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                // 表示没有访问过
                if (!visited[newi][newj]){
                    boolean flag=check(board,visited,newi,newj,word,k+1);
                    if (flag){
                        result=true;
                        break;
                    }
                }
            }
        }
        // 设置回来 表示的没有访问过。
        visited[i][j]=false;
        return result;
    }
}
